#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 100;
const int maxn = 5 + 2e5;

int n, m, mod;

void exgcd(ll a, ll b, ll &x, ll &y, ll &g) {
    if (b == 0)
        x = 1, y = 0, g = a;
    else
        exgcd(b, a % b, y, x, g), y -= a / b * x;
}

ll inv(ll a, ll b) { // ax = 1 mod b
    ll x, y, g;
    exgcd(a, b, x, y, g);
    return g == 1 ? (x + b) % b : -1;
}

inline ll fx(ll x) { return ((1 + x) * inv((1 - x + mod) % mod, mod)) % mod; }

struct Node {
    int to, w;
};
vector<Node> adj[maxn * 4];

inline void add(int l, int r, int w) {
    adj[l + 0 * n].push_back({r + 1 * n, w}), w = fx(w);
    adj[l + 1 * n].push_back({r + 2 * n, w}), w = fx(w);
    adj[l + 2 * n].push_back({r + 3 * n, w}), w = fx(w);
    adj[l + 3 * n].push_back({r + 0 * n, w}), w = fx(w);
}

bool visit[maxn * 4];
ll dis[maxn * 4];

struct cmp {
    bool operator()(int l, int r) { return dis[l] > dis[r]; }
};

void dijkstra() {
    priority_queue<int, vector<int>, cmp> qe;
    memset(dis, inf, sizeof(dis));
    dis[1] = 0, visit[1] = 1, qe.push(1);
    while (!qe.empty()) {
        int now = qe.top();
        qe.pop();
        for (auto p : adj[now]) {
            if (visit[p.to]) continue;
            visit[p.to] = 1, dis[p.to] = dis[now] + p.w, qe.push(p.to);
        }
    }
}

int main() {
    n = rad(), m = rad(), mod = rad();
    rf(i, m) {
        int l = rad(), r = rad(), w = rad();
        add(l, r, w);
        // rf(j, 4) printf("%d ", w), w = fx(w);
        // puts("ed");
    }
    dijkstra();
    // rf(i, 4) printf("%d ", dis[i * n]);
    // puts("ed");
    printf("%lld", min(min(min(dis[n], dis[2 * n]), dis[3 * n]), dis[4 * n]));
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}

/*
5 5 11
1 2 3
2 3 4
3 4 5
4 5 6
1 3 7
*/